﻿Imports System
Imports System.Collections.Generic
Imports System.Collections.ObjectModel
Imports System.Runtime.CompilerServices
Imports System.Runtime.InteropServices

Namespace System.Workflow.Runtime
    <Serializable> _
    Friend Class KeyedPriorityQueue([Of] K, V As Class, P)
        ' Events
        Public Custom Event FirstElementChanged As EventHandler([Of] KeyedPriorityQueueHeadChangedEventArgs([Of] V))

        ' Methods
        Public Sub New()
            Me.heap = New List([Of] HeapNode([Of] K, V, P, K, V, P))
            Me.priorityComparer = Comparer([Of] P).Default
            Me.placeHolder = New HeapNode([Of] K, V, P, K, V, P)
            Me.heap.Add(New HeapNode([Of] K, V, P, K, V, P))
        End Sub

        Public Sub Clear()
            Me.heap.Clear
            Me.size = 0
        End Sub

        Public Function Dequeue() As V
            Dim local As V = If((Me.size < 1), CType(Nothing, V), Me.DequeueImpl)
            Dim newHead As V = If((Me.size < 1), CType(Nothing, V), Me.heap.Item(1).Value)
            Me.RaiseHeadChangedEvent(CType(Nothing, V), newHead)
            Return local
        End Function

        Private Function DequeueImpl() As V
            Dim local As V = Me.heap.Item(1).Value
            Me.heap.Item(1) = Me.heap.Item(Me.size)
            Me.heap.Item(Me.size--) = Me.placeHolder
            Me.Heapify(1)
            Return local
        End Function

        Public Sub Enqueue(ByVal key As K, ByVal value As V, ByVal priority As P)
            Dim local As V = If((Me.size > 0), Me.heap.Item(1).Value, CType(Nothing, V))
            Dim num As Integer = ++Me.size
            Dim num2 As Integer = (num / 2)
            If (num = Me.heap.Count) Then
                Me.heap.Add(Me.placeHolder)
            End If
            Do While ((num > 1) AndAlso Me.IsHigher(priority, Me.heap.Item(num2).Priority))
                Me.heap.Item(num) = Me.heap.Item(num2)
                num = num2
                num2 = (num / 2)
            Loop
            Me.heap.Item(num) = New HeapNode([Of] K, V, P, K, V, P)(key, value, priority)
            Dim newHead As V = Me.heap.Item(1).Value
            If Not newHead.Equals(local) Then
                Me.RaiseHeadChangedEvent(local, newHead)
            End If
        End Sub

        Public Function FindByPriority(ByVal priority As P, ByVal match As Predicate([Of] V)) As V
            If (Me.size >= 1) Then
                Return Me.Search(priority, 1, match)
            End If
            Return CType(Nothing, V)
        End Function

        Private Sub Heapify(ByVal i As Integer)
            Dim num As Integer = (2 * i)
            Dim num2 As Integer = (num + 1)
            Dim j As Integer = i
            If ((num <= Me.size) AndAlso Me.IsHigher(Me.heap.Item(num).Priority, Me.heap.Item(i).Priority)) Then
                j = num
            End If
            If ((num2 <= Me.size) AndAlso Me.IsHigher(Me.heap.Item(num2).Priority, Me.heap.Item(j).Priority)) Then
                j = num2
            End If
            If (j <> i) Then
                Me.Swap(i, j)
                Me.Heapify(j)
            End If
        End Sub

        Protected Overridable Function IsHigher(ByVal p1 As P, ByVal p2 As P) As Boolean
            Return (Me.priorityComparer.Compare(p1, p2) < 1)
        End Function

        Public Function Peek() As V
            If (Me.size >= 1) Then
                Return Me.heap.Item(1).Value
            End If
            Return CType(Nothing, V)
        End Function

        Private Sub RaiseHeadChangedEvent(ByVal oldHead As V, ByVal newHead As V)
            If (Not oldHead Is newHead) Then
                Dim firstElementChanged As EventHandler([Of] KeyedPriorityQueueHeadChangedEventArgs([Of] V)) = Me.FirstElementChanged
                If (Not firstElementChanged Is Nothing) Then
                    firstElementChanged.Invoke(Me, New KeyedPriorityQueueHeadChangedEventArgs([Of] V)(oldHead, newHead))
                End If
            End If
        End Sub

        Public Function Remove(ByVal key As K) As V
            If (Me.size >= 1) Then
                Dim oldHead As V = Me.heap.Item(1).Value
                Dim i As Integer = 1
                Do While (i <= Me.size)
                    If Me.heap.Item(i).Key.Equals(key) Then
                        Dim local2 As V = Me.heap.Item(i).Value
                        Me.Swap(i, Me.size)
                        Me.heap.Item(Me.size--) = Me.placeHolder
                        Me.Heapify(i)
                        Dim local3 As V = Me.heap.Item(1).Value
                        If Not oldHead.Equals(local3) Then
                            Me.RaiseHeadChangedEvent(oldHead, local3)
                        End If
                        Return local2
                    End If
                    i += 1
                Loop
            End If
            Return CType(Nothing, V)
        End Function

        Private Function Search(ByVal priority As P, ByVal i As Integer, ByVal match As Predicate([Of] V)) As V
            Dim local As V = CType(Nothing, V)
            If Me.IsHigher(Me.heap.Item(i).Priority, priority) Then
                If match.Invoke(Me.heap.Item(i).Value) Then
                    local = Me.heap.Item(i).Value
                End If
                Dim num As Integer = (2 * i)
                Dim num2 As Integer = (num + 1)
                If ((local Is Nothing) AndAlso (num <= Me.size)) Then
                    local = Me.Search(priority, num, match)
                End If
                If ((local Is Nothing) AndAlso (num2 <= Me.size)) Then
                    local = Me.Search(priority, num2, match)
                End If
            End If
            Return local
        End Function

        Private Sub Swap(ByVal i As Integer, ByVal j As Integer)
            Dim node As HeapNode([Of] K, V, P, K, V, P) = Me.heap.Item(i)
            Me.heap.Item(i) = Me.heap.Item(j)
            Me.heap.Item(j) = node
        End Sub


        ' Properties
        Public ReadOnly Property Count As Integer
            Get
                Return Me.size
            End Get
        End Property

        Public ReadOnly Property Keys As ReadOnlyCollection([Of] K)
            Get
                Dim list As New List([Of] K)
                Dim i As Integer = 1
                Do While (i <= Me.size)
                    list.Add(Me.heap.Item(i).Key)
                    i += 1
                Loop
                Return New ReadOnlyCollection([Of] K)(list)
            End Get
        End Property

        Public ReadOnly Property Values As ReadOnlyCollection([Of] V)
            Get
                Dim list As New List([Of] V)
                Dim i As Integer = 1
                Do While (i <= Me.size)
                    list.Add(Me.heap.Item(i).Value)
                    i += 1
                Loop
                Return New ReadOnlyCollection([Of] V)(list)
            End Get
        End Property


        ' Fields
        Private FirstElementChanged As EventHandler([Of] KeyedPriorityQueueHeadChangedEventArgs([Of] V))
        Private heap As List([Of] HeapNode([Of] K, V, P, K, V, P))
        Private placeHolder As HeapNode([Of] K, V, P, K, V, P)
        Private priorityComparer As Comparer([Of] P)
        Private size As Integer

        ' Nested Types
        <Serializable, StructLayout(LayoutKind.Sequential)> _
        Private Structure HeapNode([Of] KK, VV, PP)
            Public Key As KK
            Public Value As VV
            Public Priority As PP
            Public Sub New(ByVal key As KK, ByVal value As VV, ByVal priority As PP)
                Me.Key = key
                Me.Value = value
                Me.Priority = priority
            End Sub
        End Structure
    End Class
End Namespace

